/**
 * https://leetcode.cn/problems/trapping-rain-water/submissions/584437953/
 * 42. 接雨水
 * difficulty 2024.12.02
 * 单调栈
 */

class Solution {
public:
    int trap(vector<int>& height) {
        int i=0;
        int n=height.size();
        while(i<n-1&&height[i]<height[i+1])
        i++;
        int cur=i;
        int sum=0;
        int d=0;
        for(;i<n;++i){
            if(height[i]>=height[cur]){
                sum+=d;
                d=0;
                cur=i;
            }else
            d+=(abs(height[i]-height[cur]));
        }
        // cout<<sum<<endl;
        d=n-1;
        for(int i=n-2;i>cur;--i){
            if(height[i]<height[d])
                sum+=(height[d]-height[i]);
                else
                    d=i;
        }
        return sum;
    }
};